package code2;

import code1.ArrayGenerator;
import code1.SortHelper;

import java.util.Arrays;
import java.util.Random;


/**
 * @author noob
 * @version 1.0
 * @date 2021/3/16 18:13
 * 双路快速排序
 * 最差时间复杂度O(n)
 * 期望时间复杂度 O(logn)
 *
 * arr[i] < V i++
 * arr[j] > V j--
 * i >= j  break
 * 交换
 * i++
 * j--
 */
public class QuickSortI {


    public static <E extends Comparable<E>> void sort(E[] arr){
            quickSort(arr,0,arr.length-1);
    }

    private static <E extends Comparable<E>> void quickSort(E[] arr, int left, int right) {

        if(left > right){
            return;
        }

        int p = partition(arr,left,right);
        quickSort(arr,left,p-1);
        quickSort(arr,p+1,right);

    }

    private static <E extends Comparable<E>> int partition(E[] arr, int left, int right) {

        int index = (new Random()).nextInt(right-left+1)+left;
        exchange(arr,left,index);



        int i = left+1;
        int j = right;
        while (true){
            while (i<=j && arr[i].compareTo(arr[left]) < 0){
                i++;
            }
            while (j>=i && arr[j].compareTo(arr[left]) > 0){
                j--;
            }

//            2种可能
            if(i>=j) {
                break;
            }


            exchange(arr,i,j);
            i++;
            j--;
        }

        exchange(arr,left,j);
        return j;




        //优化
//        int index = (new Random()).nextInt(right-left+1)+left;
//        exchange(arr,left,index);

//        int j = left;
//        for (int i = left+1; i <= right ; i++) {
//            if(arr[i].compareTo(arr[left]) < 0){
//                j++;
//                exchange(arr,i,j);
//            }
//            //e>v i++
//        }
//        exchange(arr,left,j);
//        return j;
    }

    private static <E extends Comparable<E>> void exchange(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
//        Integer[] arr={4,6,5,2,3,8,7,1};
//        QuickSort.sort(arr);
//        for (int i = 0; i < arr.length; i++) {
//            System.out.print(arr[i]+ " ");
//        }
//        System.out.println();


        int[]  dataSize = {100000,1000000};
        for(int n:dataSize){
//            Integer[] array = ArrayGenerator.generateRandomArray(n, n);
            Integer[] array = ArrayGenerator.generateOrderedArray(n);
            Integer[]  copy = Arrays.copyOf(array,array.length);

            SortHelper.sortTest("QuickSortI",copy);

            System.out.println("--------------------------------");
        }


    }


}
